package org.example;

class Solution {
    boolean isValid(int[] positions, int cur, int curPos) {
        for (int i = 0; i < cur; i++) {
            int dist = cur - i;
            if (curPos == positions[i] || curPos - dist == positions[i] || curPos + dist == positions[i]) {
                return false;
            }
        }
        return true;
    }

    public int dfs(int[] positions, int cur, int n) {
        if (cur == n) {
            return 1;
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            if (isValid(positions, cur, i)) {
                positions[cur] = i;
                res += dfs(positions, cur + 1, n);
            }
        }
        return res;
    }

    public int totalNQueens(int n) {
        int[] positions = new int[n];
        return dfs(positions, 0, n);
    }
}

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}